package main.java.expansion;

import main.java.utils.SortTestHelper;

import java.util.Random;

/**
 * @author Wrb
 * @date 2019/5/28 14:32
 * 查找数组中第n大的元素的位置
 */
public class SearchN {

	public int search(int[] arr,int n) {
		if (n > arr.length || n < 0) {
			return -1;
		}
		search(arr, 0, arr.length - 1, n);
		return arr[n - 1];
	}

	private void search(int[] arr, int l, int r,int n) {
		int p = partition(arr, l, r);

		if (p == n - 1) {
			return;
		}
		if (p > n - 1) {
			search(arr, l, p - 1, n);
		} else {
			search(arr, p + 1, r, n);
		}
	}

	//对数组arr[l....r]部分进行partition操作
	//返回值p 即为元素所在位置 使得arr[l...p-1]<arr[p] ， arr[p+1...r]>arr[p]
	private int partition(int[] arr, int l, int r) {
		//优化2：随机选取基准
		SortTestHelper.swap(arr, l, new Random().nextInt(r - l + 1) + l);
		int v = arr[l];
		int j = l;
		for (int i = l + 1; i <= r; i++) {
			if (arr[i] < v) {
				SortTestHelper.swap(arr, ++j, i);
			}
		}
		SortTestHelper.swap(arr, l, j);
		return j;
	}

	public static void main(String[] args) {
		SearchN searchN = new SearchN();
		int n = 100;
		int arr[] = SortTestHelper.generateRandomArray(n, 0, n);
//		int arr[] = SortTestHelper.generateNealyOrderedArray(n, 10);
		SortTestHelper.printArray(arr,n);
		System.out.println(searchN.search(arr, 60));
		SortTestHelper.printArray(arr,n);
	}
}
